package match

// kmp kmp算法
func kmp(modelStr, mainStr string) int {

	nextArray := generateNextArray(modelStr)
	j := 0
	for i := 0; i < len(modelStr); i++ {
		// 如果遇到坏字符
		for j > 0 && modelStr[i] != mainStr[j] {
			// 找到坏字符之后，将模式串移动到对应前缀和可匹配后缀对齐的位置，也就是将j移动到k，然后再从j位置继续比较
			// 如果失效函数值为-1，则j为0，相当于将主串中的坏字符位置i和模式串开头重新比较
			j = nextArray[j-1] + 1
		}
		// 对比下来如果相等则将模式串下标移动一位
		if modelStr[j] == mainStr[i] {
			j++
		}
		// 模式串下标可以移动到尾部，说明已经找到完全匹配的子串，可以直接返回结果，i - j
		if j == len(modelStr) {
			return i - len(modelStr) + 1
		}
	}

	return -1
}

// generateNextArray 生成next数组
func generateNextArray(modelStr string) []int {
	// TODO 这部分还没看懂，先不看了
	return nil
}

// boyerMoore BM 算法,假设匹配的字符串只有字母
func boyerMoore(modelStr, mainStr string) int {

	// 预处理模式串 坏字符哈希表
	bc := generateBC(modelStr)
	// 预处理模式串 suffix 数组 、prefix 数组
	gs, bs := generateGS(modelStr)
	// 主串和模式串匹配的第一个字符

	for i := 0; i < len(mainStr)-len(modelStr); i++ {
		// 模式串从后往前比较，表示模式串中比对字符的定位
		j := len(modelStr)
		for ; j >= 0; j-- {
			// 发现坏字符
			if modelStr[j] != mainStr[i+j] {
				break
			}
		}
		// 模式串和主串的子串完全匹配
		if j < 0 {
			return i
		}

		// 通过坏字符规则计算出来的移动位置
		x := j - bc[int(modelStr[i+j])]
		y := 0
		// 发现坏字符的位置在最后一个字符之前，也就是说存在好后缀
		// 依据好后缀规则也计算一次移动位置
		if j < len(modelStr)-1 {
			y = moveByGS(j, len(modelStr), gs, bs)
		}
		i = x
		if x < y {
			i = y
		}

	}
	return -1
}

// moveByGS 依据好后缀规则计算移动位置
func moveByGS(j int, m int, gs []int, bs []bool) int {
	// 好后缀的长度
	k := m - 1 - j
	// 先看是否能找到另一个子串
	if gs[k] != -1 {
		// 能找到则移动到另一个子串和好后缀对齐
		return j - gs[j-1] + 1
	}

	for r := j + 2; r < m-1; r++ {
		if bs[m-r] {
			return r
		}
	}
	return m
}

// generateGS 生成suffix数组 后缀的另一个出现的位置
func generateGS(modelStr string) ([]int, []bool) {
	// 长度为k后缀的的另外一个子串的起始下标
	gs := make([]int, len(modelStr)-1)
	// 长度为k的后缀是否有匹配的前缀
	ps := make([]bool, len(modelStr)/2)
	// 初始化
	for i := 0; i < len(gs); i++ {
		gs[i] = -1
		ps[i] = false
	}
	// 外层循环控制后缀长度，内层逐一比对
	// i表示后缀的长度范围为 0 ～ m-2
	for i := 1; i < len(modelStr)-1; i++ {
		// j控制要求公共后缀子串的子串长度
		j := i
		// k 表示公共后缀子串长度
		k := 0
		// modelStr 与 0～m-1求公共后缀子串
		// 从后向前比较查找公共后缀子串，子串长度K不能比j大
		//长度为l-1的后缀在模式串中存在另一个匹配串的情况下，长度为l的后缀子串在模式串中的另外一个后缀子串才存在
		// k始终从0开始，即后缀子串的长度始终从1开始比对，
		for j >= 0 && modelStr[j] == modelStr[len(modelStr)-1-k] {
			// 下次要比对的字符向前移动一位
			j--
			// 由于匹配成功，长度+1
			k++
			gs[k] = j + 1
		}
		// j 为 -1 说明当前长度后缀和模式串前缀匹配成功
		if j == -1 {
			ps[k] = true
		}
	}

	return gs, ps
}

// generateBC 定位坏字符出现的位置
func generateBC(modelStr string) []int {
	bc := make([]int, 256)
	for i := 0; i < len(bc); i++ {
		bc[i] = -1
	}
	for i, s := range modelStr {
		bc[int(s)] = i
	}

	return bc
}

// rabinKarp rk算法
func rabinKarp(modelStr, mainStr string) int {
	if len(mainStr) < len(modelStr) {
		return -1
	}
	// 模式串哈希值计算
	modelHash := hashStr(modelStr)
	mainStrHashArray := make([]int, len(mainStr)-len(modelStr)+1)
	// 主串计算hash值，相邻两个子串间的hash值有交集
	mainStrHashArray[0] = hashStr(mainStr[0:len(modelStr)])
	for i := 1; i < len(mainStr)-len(modelStr)+1; i++ {
		pre := mainStrHashArray[i-1]
		mainStrHashArray[i] = pre - int(mainStr[i-1]) + int(mainStr[i+len(modelStr)-1])
	}
	// 对比主串的子串和模式串的hash值
	for i := 0; i < len(mainStrHashArray); i++ {
		if modelHash == mainStrHashArray[i] {
			// 进一步比对每个字节是否相等
			j := 0
			for ; j < len(modelStr) && modelStr[j] == mainStr[i+j]; j++ {
			}
			if j == len(modelStr) {
				return i
			}
			continue
		}
	}

	return -1
}

func hashStr(str string) int {

	result := 0
	for _, s := range str {
		result += int(s)
	}

	return result
}

// bruteForce 暴力匹配算法
func bruteForce(modelStr, mainStr string) int {
	if len(mainStr) < len(modelStr) {
		return -1
	}

	for j := 0; j < len(mainStr); j++ {
		for i := 0; i < len(modelStr); i++ {
			if mainStr[j+i] != modelStr[i] {
				break
			}
			if i == len(modelStr)-1 {
				return j
			}
		}
	}

	return -1
}
